/**
 * 项目名称: 快速排序.cpp
 * 项目路径: study/DataStructure/数据结构/排序/交换排序
 * 编辑时间: 2024年08月26日16时59分43秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 用一个元素将待排序序列划分成左右两个部分
 * @param A
 * @param low
 * @param high
 * @return
 */
int Partition(int A[], int low, int high) {
    int pivot = A[low];//第一个元素作为枢轴
    while (low < high) {//用low,high搜索枢轴的最终元素
        while (low < high && A[high] >= pivot)--high;
        A[low] = A[high];//比枢轴小的元素移动到左端
        while (low < high && A[low] <= pivot)++low;
        A[high] = A[low];//比枢轴大的元素移动到右端
    }
    A[low] = pivot;//枢轴元素存放到最终位置
    return low;//返回存放枢轴的最终位置
}

/**
 * 快速排序
 * @param A
 * @param low 0
 * @param high A.size - 1
 */
void QuickSort(int A[], int low, int high) {
    if (low < high) {//递归跳出的条件
        int pivot = Partition(A, low, high);//划分
        QuickSort(A, low, pivot);//划分左子表
        QuickSort(A, pivot + 1, high);//划分右子表
    }
}
